Key management is of crucial importance in any system for selective access to information, such as broadcast or multicast protection systems. Broadcast and multicast enables efficient distribution of protected information to large groups of receivers, as schematically illustrated in FIG. 1, for both wireless applications and standard data communications. In the following the term broadcast will be used to refer to both broadcast and multicast. Recent efforts focus on broadcast over wireless networks and a key topic is to use the wireless link as efficiently as possible, for example to reduce time for media access. Another topic of key interest is to provide secure broadcast. Thus, encryption of protected information is an important enabler for commercial broadcast services. Commercial broadcast involve several parties, e.g. the users receiving broadcasted protected information, the network provider, and the content provider. In order to direct broadcast only to users that fulfill the commercial requirements the content provider provides valid encryption keys to these users in a key distribution process. As the group of active listeners is dynamic and changing over time the update of keys becomes an important topic. From a user point of view it is important that a key update is fast, eliminating annoying waiting time. From the point of view of network provider and/or content provider it is also important that a key update is made as fast and efficient as possible to save valuable wireless resources.
Broadcast protection systems normally operate with a number of distinguished steps. A service registration step is usually required in which a user enters an agreement with a service provider. In this step the user is provided with a personal, unique and secret key. In a key-distribution step a media key (or more generally an information protection key) is distributed to registered users for decryption of broadcast protected information. The service provider encrypts the protected information in a media delivery protection step. A re-key step is required to update the protected information key, e.g. when a new user is registered, a user de-registers or when a media key is compromised. Periodic re-key may also be used to increase the security of the system. Service registration is usually point-to-point between a user and a content provider and may use any secure and authenticated means for communication. Key-distribution and media delivery protection (MDP) will be executed in a one-to-many fashion.
The main problem with key-distribution is to update the MDP-key as fast as possible when new users either join or leave the group in a way, which is scalable to large groups. The naive approach of sending the updated MDP-key encrypted individually for each user does not scale well and it is resource consuming, increasing both computational cost and bandwidth consumption.
There are schemes proposed, referred to as group-key distribution protocols to improve scalability e.g. LKH (Logical Key Hierarchy), SD (Subset Difference) and LSD (Layered Subset Difference). These are examples of hierarchical group key distribution protocols.
To each hierarchical group key distribution protocol there is an associated set of encryption keys. An abstract hierarchical tree can be used in order to illustrate the arrangement of these keys and the relationship between the keys. FIG. 2 illustrates a hierarchical tree with a set of users, U1 to U8, at the bottom. At the top of the hierarchy there is the output key KM of the specific hierarchical protocol. A subgroup of the complete group of users determines a sub-tree of the hierarchical tree that in turn determines a group key management message comprising a set of identifiable message elements. The nodes in the tree model in between the bottom and top levels are associated with encryption keys required for decrypting elements of the group key management message. Each user receives, in an initiation phase, information for deriving a subset of these keys, e.g. all keys on the path between the particular user Mi and the KM. The hierarchical group key distribution protocols provide linear initial keying performance and improved logarithmic re-key performance. These methods are the most scalable and efficient ones because of the non-linear performance.
FIG. 2 can conveniently be used to discuss the LKH method. The LKH method is a scalable group-key distribution protocol, which is based on the approach of associating every node (i) in a tree with a key Ki where (i) is an index in one or several dimensions. The root key, KM is the key associated with the top level of the tree and it is used as the MDP-key. Every user in the group of users is provided with individual keys, e.g. in a registration phase, and these keys are associated with the leaves K(rst) at the bottom of the tree. Every user also receives all the keys lying on the path from its leaf up to the root. A typical message is made of triplets {i, j, [Ki]Kj}, where i>j denoting that node i is an ancestor to node j. A user can decrypt the message part if j is on the path up to the root i.e. Ki can be retrieved by use of the key Kj associated with node j. Thus, the set of Ki comprises hierarchical encryptions of the root key KM. When updating the MDP-key because of a joining or leaving user, the numbers of required messages are few, as well as the message size. A possible drawback is that the system is state-full or state-dependent, i.e. the algorithm makes use of the previous group key to encrypt the new generated group key. Therefore, the dependency of state is required for the scheme. In the case the group key for a certain state is lost it is not possible for the participant to easily re-catch the session by any means.
Another drawback is that a provided method for batch re-keying, i.e. batch update of keys, is not very efficient in particular at times of major and momentary changes of user status.
The Subset Cover algorithms is a general class of group-key distribution protocols, characterized in that a group user is associated with a subset of users, the subset being associated with a particular key. The Subset Difference (SD) protocol, illustrated in FIG. 3, is an example of these protocols. With reference to FIG. 3 the nodes are numbered with an index j. Exemplary in FIG. 3 the nodes 1-15 are indicated. A collection of subsets Si,j covers the complete group and distinctly determines the set of all users. Si,j denotes the set of leaves under node i but not under node j. In FIG. 3 the sets S2,5 and S3,12 are illustrated. When updating the MDP key, the group of users is exactly covered with these subsets, and the updated key is encrypted under each of the subset keys. The SD (Subset Difference) scheme is a stateless group-key distribution protocol, as is the more general subset cover (SC) protocol. The SD scheme creates a binary tree with as many leaves as possible users. The number of leaves in a structure is fixed. Some leaves are occupied by active users, some with revoked users or users having left the broadcast, and some leaves are not occupied but free for new users to join the broadcast. The key server (KS) creates the set S of entities Si,j. Every Si,j is also uniquely associated with a key Lij, which every user of the set Si,j can compute, but no other group user. The MDP-key can be updated to a particular set Si,j by encrypting it using Lij. It should be noted that this has to be done for every Si,j belonging to S. The Lij's are created in a hierarchical fashion, where a random seed associated with the node i is extended to nodes j>i using a one-way function iteratively.
The LSD (Layered Subset Difference) scheme is a SD scheme, but with special layers such that every possible user needs to store fewer keys than in the original scheme.
In all these systems, the group key management message that is broadcasted to all users is quite large.
Reference [1] discloses a stateless hierarchical method based on subset cover of the group of users.
The size of a key management message tends to become very large in large groups. Therefore, various attempts have been made to make the broadcast of a key management message as efficient as possible. Reference [2] discloses a method to arrange the users in dependence of the probability that a user will be compromised thereby allowing for an increased efficiency of the key management system.
Because of the size of a key management message it would be very resource consuming to frequently multicast or broadcast such messages over a cellular network. There is also a question which party would finance the expensive radio link resources required to transmit the messages. References [3, 4] advice a distributed system of entities each entity managing a subgroup of the full group. Each subgroup is further associated with a separate group key. Although these systems provide scalability they become complex and expensive. Another problem with the cited methods is related to distribution of security functionality to another entity whereby such other entity must be trusted to securely handle the security functionality. This makes such systems more exposed to compromise. As a consequence, such systems do not manage optimizations done by entities not trusted with keys or other secret information.
In addition there are practical problems arising when keys are to be distributed relating to more than one media session at the same time. An example could be a service provider that offers a plurality of channels independently selected. The systems referred to above do not provide an easy manner to manage multiple channels and where each of these may be turned on and off by a user as desired. The naive method would be to use a separate system for each channel, which, however, would be very inefficient.
A disadvantage of stateless schemes such as SD is that at every key update, the size of the key management message depends on the total number of users revoked from the system. Thus, if only one user shall be revoked in a key update, the message size still depends on the total number of users that have already been revoked. In the state-full LKH system, the revocation of one user does not depend on the total number of already revoked users, but is instead dependent on the logarithmic number of existing users.
Thus, there is a need for an efficient and reliable method for group-key distribution in broadcast and multicast systems that overcome the drawbacks of prior art systems. In particular there is a need for a method that provides for optimization of the message size.